package com.peng.linkedlist;

import java.util.Arrays;

/**
 * 把链表分成 小于、等于、大于三块链表， 并连接起来
 */
public class Test03_SmallerEqualBigger {

    public static Node getSmallerEqualBigger(Node head, int pivot) {
        if (head == null) {
            return null;
        }

        //小于区的链表
        Node sHead = null;
        Node sTail = null;


        //等于区的链表
        Node eHead = null;
        Node eTail = null;

        //大于区的链表
        Node bHead = null;
        Node bTail = null;

        Node cur = head;
        //先划分成小于、等于、大于三部分链表
        while (cur != null) {
            Node next = cur.next;
            cur.next = null;
            if (cur.value < pivot) {
                if (sHead == null) {
                    sHead = cur;
                    sTail = cur;
                } else {
                    sTail.next = cur;
                    sTail = cur;
                }
            } else if (cur.value == pivot) {
                if (eHead == null) {
                    eHead = cur;
                    eTail = cur;
                } else {
                    eTail.next = cur;
                    eTail = cur;
                }
            } else {
                if (bHead == null) {
                    bHead = cur;
                    bTail = cur;
                } else {
                    bTail.next = cur;
                    bTail = cur;
                }
            }

            cur = next;
        }


        if (sTail != null) {
            sTail.next = eHead;
            eTail = eHead == null ? sTail : eTail;
        }
        if (eTail != null) {
            eTail.next = bHead;
        }

        return sHead != null ? sHead : (eHead != null ? eHead : bHead);


    }

    public static void main(String[] args) {
        Node head = LinkedListUtils.link(Arrays.asList(
                new Node(1),
                new Node(2),
                new Node(3),
                new Node(5),
                new Node(7),
                new Node(3),
                new Node(8),
                new Node(3)
        ));
        LinkedListUtils.printNodes(head);
        Node node = getSmallerEqualBigger(head, 3);
        LinkedListUtils.printNodes(node);
    }
}
